//Cracking Coding Interview 4.5
// check if a BT is BST
//5:10PM--5:19PM--5:26PM(bugfree)

#include<iostream>
#include<vector>
#include<list>

using namespace std;

struct Node {
	Node(int ikey):l(NULL), r(NULL){
		key=ikey;
	}
	Node():l(NULL), r(NULL){}
	int key;
	Node *l, *r;
};

void InOrder(Node* tr, list<int> &seqlist) {
	if(!tr) return;
	if (tr->l) {
		InOrder(tr->l, seqlist);
	}
	seqlist.push_back(tr->key);
	if (tr->r) {
		InOrder(tr->r, seqlist);
	}
}

bool CheckBST1(Node *tr) {
	list<int> seqlist;
	InOrder(tr, seqlist);
	list<int>::iterator iter;
	int preVal=INT_MIN;
	for(iter=seqlist.begin(); iter!=seqlist.end(); iter++) {
		if(*iter<preVal) {
			return false;
		} else {
			preVal=*iter;
		}
	}
	return true;
}

bool CheckBST2(Node *tr, int imin=INT_MIN, int imax=INT_MAX) {
	if(!tr) return true;
	bool retVal=true;
	if(tr->key<imin || tr->key>imax) {
		retVal=false;
	}
	if (tr->l) {
		retVal = (retVal && CheckBST2(tr->l, imin, tr->key));
	}
	if (tr->r) {
		retVal = (retVal && CheckBST2(tr->r, tr->key, imax));
	}

	return retVal;
}

int main(int argc, char* argv[]) {
	Node nd[3];
	nd[0].key=1;
	nd[1].key=2;
	nd[2].key=3;
	nd[1].l=&nd[0];
	nd[1].r=&nd[2];

	bool bBST=CheckBST2(&nd[1]);
	cout<<bBST<<endl;

	return 0;
}